{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Shortest Cycle in a Graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #graph"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #图"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: findShortestCycle"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #图中的最短环"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>现有一个含 <code>n</code> 个顶点的 <strong>双向</strong> 图，每个顶点按从 <code>0</code> 到 <code>n - 1</code> 标记。图中的边由二维整数数组 <code>edges</code> 表示，其中 <code>edges[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> 表示顶点 <code>u<sub>i</sub></code> 和 <code>v<sub>i</sub></code> 之间存在一条边。每对顶点最多通过一条边连接，并且不存在与自身相连的顶点。</p>\n",
    "\n",
    "<p>返回图中 <strong>最短</strong> 环的长度。如果不存在环，则返回 <code>-1</code> 。</p>\n",
    "\n",
    "<p><strong>环</strong> 是指以同一节点开始和结束，并且路径中的每条边仅使用一次。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/01/04/cropped.png\" style=\"width: 387px; height: 331px;\">\n",
    "<pre><strong>输入：</strong>n = 7, edges = [[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>长度最小的循环是：0 -&gt; 1 -&gt; 2 -&gt; 0 \n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2023/01/04/croppedagin.png\" style=\"width: 307px; height: 307px;\">\n",
    "<pre><strong>输入：</strong>n = 4, edges = [[0,1],[0,2]]\n",
    "<strong>输出：</strong>-1\n",
    "<strong>解释：</strong>图中不存在循环\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>2 &lt;= n &lt;= 1000</code></li>\n",
    "\t<li><code>1 &lt;= edges.length &lt;= 1000</code></li>\n",
    "\t<li><code>edges[i].length == 2</code></li>\n",
    "\t<li><code>0 &lt;= u<sub>i</sub>, v<sub>i</sub> &lt; n</code></li>\n",
    "\t<li><code>u<sub>i</sub> != v<sub>i</sub></code></li>\n",
    "\t<li>不存在重复的边</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [shortest-cycle-in-a-graph](https://leetcode.cn/problems/shortest-cycle-in-a-graph/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [shortest-cycle-in-a-graph](https://leetcode.cn/problems/shortest-cycle-in-a-graph/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['7\\n[[0,1],[1,2],[2,0],[3,4],[4,5],[5,6],[6,3]]', '4\\n[[0,1],[0,2]]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for s,e in edges:\n",
    "            g[s].append(e)\n",
    "            g[e].append(s)\n",
    "        def bfs(start,target):\n",
    "            dis=[inf]*n\n",
    "            dis[start]=0\n",
    "            q= collections.deque()\n",
    "            q.append(start)\n",
    "            while q:\n",
    "                u=q.popleft()\n",
    "                if u==target:\n",
    "                    return dis[target]\n",
    "                for v in g[u]:\n",
    "                    if u==start and v==target:continue\n",
    "                    if dis[v]>dis[u]+1:\n",
    "                        dis[v]=dis[u]+1\n",
    "                        q.append(v)\n",
    "            return inf \n",
    "        ans=inf\n",
    "        for i in range(n):\n",
    "            for j in g[i]:\n",
    "                ans=min(ans,bfs(i,j)+1)\n",
    "        return ans if ans!=inf else -1\n",
    "                    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        e = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            e[x].append(y)\n",
    "            e[y].append(x)\n",
    "        \n",
    "        def bfs(i):\n",
    "            d = {i: 0}\n",
    "            q = deque()\n",
    "            q.append(i)\n",
    "            res = 10 ** 5\n",
    "            while q:\n",
    "                tmp = q.popleft()\n",
    "                # print(tmp)\n",
    "                for ne in e[tmp]:\n",
    "                    if ne in d.keys():\n",
    "                        if d[ne] == d[tmp] or d[ne] == d[tmp] + 1:\n",
    "                            # print(\"d[ne], d[tmp]\", d[ne], d[tmp])\n",
    "                            res = min(res, d[ne] + d[tmp] + 1)\n",
    "                    else:\n",
    "                        d[ne] = d[tmp] + 1\n",
    "                        q.append(ne)\n",
    "                # print(tmp, q, d)\n",
    "            return res\n",
    "\n",
    "        res = 10 ** 5\n",
    "        # ans = bfs(1)\n",
    "        # print(ans)\n",
    "        for i in range(n):\n",
    "            res = min(res, bfs(i))\n",
    "        return res if res != 10 ** 5 else -1\n",
    "\n",
    "                    \n",
    "\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        neighbors = [[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            neighbors[edge[0]].append(edge[1])\n",
    "            neighbors[edge[1]].append(edge[0])\n",
    "        def circle(start):\n",
    "            degs = [-1] * n\n",
    "            degs[start] = 0\n",
    "            q = deque([(-1, start)])\n",
    "            circle = False\n",
    "            ans = n + 1\n",
    "            while len(q) > 0:\n",
    "                lq = len(q)\n",
    "                for _ in range(lq):\n",
    "                    f, i = q.popleft()\n",
    "                    for j in neighbors[i]:\n",
    "                        if j != f:\n",
    "                            if degs[j] == -1:\n",
    "                                degs[j] = degs[i] + 1\n",
    "                                q.append((i, j))\n",
    "                            else:\n",
    "                                circle = True\n",
    "                                ans = min(ans, degs[j] + degs[i] + 1)\n",
    "                if circle: return ans\n",
    "            return -1\n",
    "            \n",
    "        ans = n + 1\n",
    "        for i in range(n):\n",
    "            c = circle(i)\n",
    "            if (c > -1): ans = min(ans, c)\n",
    "        return -1 if (ans == n + 1) else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "#         g = [[] for _ in range(n)]\n",
    "#         for x, y in edges:\n",
    "#             g[x].append(y)\n",
    "#             g[y].append(x)  # 建图\n",
    "\n",
    "#         def bfs(start: int) -> int:\n",
    "#             ans = inf\n",
    "#             dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "#             dis[start] = 0\n",
    "#             q = deque([(start, -1)])\n",
    "#             while q:\n",
    "#                 x, fa = q.popleft()\n",
    "#                 for y in g[x]:\n",
    "#                     if dis[y] < 0:  # 第一次遇到\n",
    "#                         dis[y] = dis[x] + 1\n",
    "#                         q.append((y, x))\n",
    "#                     elif y != fa:  # 第二次遇到\n",
    "#                         ans = min(ans, dis[x] + dis[y] + 1)\n",
    "#             return ans\n",
    "\n",
    "#         ans = min(bfs(i) for i in range(n))\n",
    "#         return ans if ans < inf else -1\n",
    "\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for i, j in edges:\n",
    "            adj[i].append(j)\n",
    "            adj[j].append(i)\n",
    " \n",
    "        def dijkstra(i, prev):\n",
    "            cost = [inf] * n\n",
    "            q = [(0, i, prev)]\n",
    "            cost[i] = 0\n",
    "            ans = inf\n",
    "            while q:\n",
    "                pay, cur, prev = heapq.heappop(q)\n",
    "                if cost[cur] < pay:\n",
    "                    continue \n",
    "                for nxt in adj[cur]:\n",
    "                    if nxt != prev:\n",
    "                        ans = min(ans, pay + cost[nxt] + 1)\n",
    "                        if cost[nxt] > pay + 1:\n",
    "                            cost[nxt] = pay + 1\n",
    "                            heapq.heappush(q, (cost[nxt], nxt, cur))\n",
    "            return ans\n",
    "        \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            k = dijkstra(i, -1)\n",
    "            ans = min(ans, k)\n",
    "        \n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "        \n",
    "# class Solution:\n",
    "#     def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "#         ans = n + 1\n",
    "#         visited = [False] * n\n",
    "#         graph = [[] for _ in range(n)]\n",
    "#         for u, v in edges:\n",
    "#             graph[u].append(v)\n",
    "#             graph[v].append(u)\n",
    "#         for i in range(n):\n",
    "#             if not visited[i]:\n",
    "#                 visited[i] = True\n",
    "#                 q = [(i, 0, None)]\n",
    "#                 f = 0\n",
    "#                 candidates = []\n",
    "#                 can_set = set()\n",
    "#                 while f < len(q):\n",
    "#                     x, d, p = q[f]\n",
    "#                     f += 1\n",
    "#                     for v in graph[x]:\n",
    "#                         if v == p:\n",
    "#                             continue\n",
    "#                         if visited[v]:\n",
    "#                             if v not in can_set:\n",
    "#                                 can_set.add(v)\n",
    "#                                 candidates.append(v)\n",
    "#                         else:\n",
    "#                             visited[v] = True\n",
    "#                             q.append((v, d + 1, x))\n",
    "#                 for j in candidates:\n",
    "#                     q = [(j, 0, None)]\n",
    "#                     f = 0\n",
    "#                     dist = {j: 0}\n",
    "#                     while f < len(q):\n",
    "#                         x, d, p = q[f]\n",
    "#                         f += 1\n",
    "#                         if d + d >= ans:\n",
    "#                             break\n",
    "#                         for v in graph[x]:\n",
    "#                             if v == p:\n",
    "#                                 continue\n",
    "#                             if v in dist:\n",
    "#                                 ans = min(ans, dist[v] + d + 1)\n",
    "#                             else:\n",
    "#                                 dist[v] = d + 1\n",
    "#                                 q.append((v, d + 1, x))\n",
    "#         if ans > n:\n",
    "#             return -1\n",
    "#         else:\n",
    "#             return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 【1】把环分解为两段从而来判断\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y),g[y].append(x)  # 建图\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n",
    "# 【2】使用狄克斯特拉算法就是比较慢\n",
    "# class Solution:\n",
    "#     def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "#         adj = [[] for _ in range(n)]\n",
    "#         for i, j in edges:\n",
    "#             adj[i].append(j)\n",
    "#             adj[j].append(i)\n",
    " \n",
    "#         def dijkstra(i, prev):\n",
    "#             cost = [inf] * n\n",
    "#             q = [(0, i, prev)]\n",
    "#             cost[i] = 0\n",
    "#             ans = inf\n",
    "#             while q:\n",
    "#                 pay, cur, prev = heapq.heappop(q)\n",
    "#                 if cost[cur] < pay:\n",
    "#                     continue \n",
    "#                 for nxt in adj[cur]:\n",
    "#                     if nxt != prev:\n",
    "#                         ans = min(ans, pay + cost[nxt] + 1)\n",
    "#                         if cost[nxt] > pay + 1:\n",
    "#                             cost[nxt] = pay + 1\n",
    "#                             heapq.heappush(q, (cost[nxt], nxt, cur))\n",
    "#             return ans\n",
    "        \n",
    "#         ans = inf\n",
    "#         for i in range(n):\n",
    "#             k = dijkstra(i, -1)\n",
    "#             ans = min(ans, k)\n",
    "        \n",
    "#         return ans if ans < inf else -1\n",
    "\n",
    "        \n",
    "# class Solution:\n",
    "#     def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "#         ans = n + 1\n",
    "#         visited = [False] * n\n",
    "#         graph = [[] for _ in range(n)]\n",
    "#         for u, v in edges:\n",
    "#             graph[u].append(v)\n",
    "#             graph[v].append(u)\n",
    "#         for i in range(n):\n",
    "#             if not visited[i]:\n",
    "#                 visited[i] = True\n",
    "#                 q = [(i, 0, None)]\n",
    "#                 f = 0\n",
    "#                 candidates = []\n",
    "#                 can_set = set()\n",
    "#                 while f < len(q):\n",
    "#                     x, d, p = q[f]\n",
    "#                     f += 1\n",
    "#                     for v in graph[x]:\n",
    "#                         if v == p:\n",
    "#                             continue\n",
    "#                         if visited[v]:\n",
    "#                             if v not in can_set:\n",
    "#                                 can_set.add(v)\n",
    "#                                 candidates.append(v)\n",
    "#                         else:\n",
    "#                             visited[v] = True\n",
    "#                             q.append((v, d + 1, x))\n",
    "#                 for j in candidates:\n",
    "#                     q = [(j, 0, None)]\n",
    "#                     f = 0\n",
    "#                     dist = {j: 0}\n",
    "#                     while f < len(q):\n",
    "#                         x, d, p = q[f]\n",
    "#                         f += 1\n",
    "#                         if d + d >= ans:\n",
    "#                             break\n",
    "#                         for v in graph[x]:\n",
    "#                             if v == p:\n",
    "#                                 continue\n",
    "#                             if v in dist:\n",
    "#                                 ans = min(ans, dist[v] + d + 1)\n",
    "#                             else:\n",
    "#                                 dist[v] = d + 1\n",
    "#                                 q.append((v, d + 1, x))\n",
    "#         if ans > n:\n",
    "#             return -1\n",
    "#         else:\n",
    "#             return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)\r\n",
    "        \r\n",
    "        def bfs(x: int) -> int:\r\n",
    "            res = inf \r\n",
    "            dis = [-1] * n \r\n",
    "            dis[x] = 0\r\n",
    "            q = deque([(x, -1)])\r\n",
    "            while q:\r\n",
    "                x, fa = q.popleft()\r\n",
    "                for y in g[x]:\r\n",
    "                    if dis[y] < 0:\r\n",
    "                        dis[y] = dis[x] + 1\r\n",
    "                        q.append((y, x))\r\n",
    "                    elif y != fa:\r\n",
    "                        res = min(res, dis[x] + dis[y] + 1)\r\n",
    "            return res \r\n",
    "        ans = min(bfs(i) for i in range(n))\r\n",
    "        return ans if ans < inf else -1\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[]for _ in range(n)]\n",
    "        for x in edges:\n",
    "            g[x[0]].append(x[1])\n",
    "            g[x[1]].append(x[0])\n",
    "        def f(st):\n",
    "           v=[-1]*n\n",
    "           v[st]=0\n",
    "           q=deque([(st,-1)])\n",
    "           ans=inf\n",
    "           while q:\n",
    "              x,fa=q.popleft()\n",
    "              for y in g[x]:\n",
    "                 if v[y]<0:\n",
    "                     v[y]=v[x]+1\n",
    "                     q.append((y,x))\n",
    "                 elif y!=fa:\n",
    "                    ans=min(v[y]+v[x]+1,ans)\n",
    "           return ans \n",
    "        ans=min(f(i) for i in range(n))\n",
    "        return ans if ans!=inf else -1                 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            vis = [-1] * n\n",
    "            q = deque()\n",
    "            q.append(start)\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append(y)\n",
    "                    elif vis[y] == -1:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "                vis[x] = 1\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\r\n",
    "        g = [[] for _ in range(n)]\r\n",
    "        for x, y in edges:\r\n",
    "            g[x].append(y)\r\n",
    "            g[y].append(x)\r\n",
    "        \r\n",
    "        def bfs(x: int) -> int:\r\n",
    "            res = inf \r\n",
    "            dis = [-1] * n \r\n",
    "            dis[x] = 0\r\n",
    "            q = [(x, -1)]\r\n",
    "            while q:\r\n",
    "                tmp = q\r\n",
    "                q = []\r\n",
    "                for x, fa in tmp:\r\n",
    "                    for y in g[x]:\r\n",
    "                        if dis[y] < 0:\r\n",
    "                            dis[y] = dis[x] + 1\r\n",
    "                            q.append((y, x))\r\n",
    "                        elif y != fa:\r\n",
    "                            res = min(res, dis[x] + dis[y] + 1)\r\n",
    "            return res \r\n",
    "        ans = min(bfs(i) for i in range(n))\r\n",
    "        return ans if ans < inf else -1\r\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        res = inf\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def bfs(x):\n",
    "            nonlocal res\n",
    "            q = [[x, -1]]\n",
    "            dist = [-1] * n\n",
    "            dist[x] = 0\n",
    "            while q:\n",
    "                x, fa = q.pop(0)\n",
    "                for y in g[x]:\n",
    "                    if dist[y] == -1:\n",
    "                        dist[y] = dist[x] + 1\n",
    "                        q.append([y, x])\n",
    "                    elif y != fa: \n",
    "                        res = min(res, dist[y] + dist[x] + 1)\n",
    "\n",
    "                \n",
    "            \n",
    "\n",
    "        for i in range(n):\n",
    "            bfs(i)\n",
    "        return -1 if res == inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        ans = n + 1\n",
    "        for i in range(n):\n",
    "            dis = [-1] * n\n",
    "            dis[i] = 0\n",
    "            q = deque([(i, -1)])\n",
    "            while q:\n",
    "                u, p = q.popleft()\n",
    "                for v in g[u]:\n",
    "                    if dis[v] < 0:\n",
    "                        dis[v] = dis[u] + 1\n",
    "                        q.append((v, u))\n",
    "                    elif v != p:\n",
    "                        ans = min(ans, dis[u] + dis[v] + 1)\n",
    "        return ans if ans <= n else -1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a)\n",
    "        res = inf\n",
    "        for i in range(n):\n",
    "            q = deque([(i, -1, 1)])\n",
    "            visit = [0]*n\n",
    "            while q:\n",
    "                now, fro, dist = q.popleft()\n",
    "                visit[now] = dist\n",
    "                if dist > n:\n",
    "                    continue\n",
    "                for nex in g[now]:\n",
    "                    if nex != fro:\n",
    "                        if visit[nex]:\n",
    "                            res = min(res, dist + visit[nex] - 1)\n",
    "                            break\n",
    "                        q.append((nex, now, dist+1))\n",
    "        return -1 if res == inf else res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = defaultdict(list)\n",
    "        for i, j in edges :\n",
    "            graph[i].append(j)\n",
    "            graph[j].append(i)\n",
    "\n",
    "        def bfs(tar) :\n",
    "            ans = inf\n",
    "            nodesColor = [0] * n\n",
    "            dist_level = [0] * n\n",
    "            q = deque([tar])\n",
    "            level = 1\n",
    "            while q:\n",
    "                for _ in range(len(q)) :\n",
    "                    v = q.popleft()\n",
    "                    nodesColor[v] = 1\n",
    "                    for w in graph[v] :\n",
    "                        if nodesColor[w] == 0 :\n",
    "                            q.append(w)\n",
    "                            nodesColor[w] = 1\n",
    "                            dist_level[w] = level\n",
    "                        elif nodesColor[w] == 1 :\n",
    "                            ans = min(ans, dist_level[w] + dist_level[v] + 1)\n",
    "                    nodesColor[v] = 2\n",
    "                level += 1\n",
    "                if ans != inf:\n",
    "                    return ans\n",
    "            return ans\n",
    "\n",
    "        ans = inf\n",
    "        for i in range(n) :\n",
    "            k = bfs(i)\n",
    "            ans = min(ans, k)\n",
    "\n",
    "        return -1 if ans == inf else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        # 对每个点都做一遍BFS，记录dist，如果dist[x] == dist[y] 或者dist[x] + 1 == dist[y]\n",
    "        # 说明遇到了环\n",
    "        def bfs(i):\n",
    "            ans = float('inf')\n",
    "            dist = [-1]*n\n",
    "            dist[i] = 0\n",
    "            q = [i]\n",
    "            level = 1\n",
    "            while q:\n",
    "                tmp = q[:]\n",
    "                q = []\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if dist[y] == -1:\n",
    "                            dist[y] = level\n",
    "                            q.append(y)\n",
    "                        else:\n",
    "                            if dist[y] == dist[x] or dist[y] == dist[x]+1:\n",
    "                                ans = min(ans, dist[x] + dist[y] + 1)\n",
    "                level += 1\n",
    "            return ans\n",
    "        \n",
    "        # 每个点做BFS\n",
    "        min_res = float('inf')\n",
    "        for i in range(n):\n",
    "            loop_len = bfs(i)\n",
    "            if loop_len!=-1:\n",
    "                min_res = min(min_res, loop_len)\n",
    "        return min_res if min_res<float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "\n",
    "        g = [[] for i in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(len(g[i])):\n",
    "                q = deque([i])\n",
    "                dis = [inf] * n\n",
    "                dis[i] = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if not (x == i and y==g[i][j]) and dis[y] == inf:\n",
    "                            dis[y] = dis[x] + 1\n",
    "                            q.append(y)\n",
    "                ans = min(ans, 1 + dis[g[i][j]])\n",
    "        \n",
    "        return ans if ans <inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "\n",
    "        g = [[] for i in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(len(g[i])):\n",
    "                q = deque([i])\n",
    "                dis = [-1] * n\n",
    "                dis[i] = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if not (x == i and y==g[i][j]) and dis[y] == -1:\n",
    "                            dis[y] = dis[x] + 1\n",
    "                            q.append(y)\n",
    "                \n",
    "                if dis[g[i][j]] != -1:\n",
    "                    ans = min(ans, 1 + dis[g[i][j]])\n",
    "        \n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def bfs(start):\n",
    "            ans = inf\n",
    "            dis = [-1] * n\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    # 访问过且非直接父节点\n",
    "                    elif y != fa:\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "        \n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        \n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 【1】把环分解为两段从而来判断：典型的BFS法则，这种方法本质上是遍历，所以速度较慢；\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y),g[y].append(x)  # 建图：邻接表\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "        ans = min(bfs(i) for i in range(n))#循环得到每个节点最小环，然后从中找到最小值；\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n",
    "# 【2】使用狄克斯特拉算法就是比较慢\n",
    "# class Solution:\n",
    "#     def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "#         adj = [[] for _ in range(n)]\n",
    "#         for i, j in edges:\n",
    "#             adj[i].append(j)\n",
    "#             adj[j].append(i)\n",
    " \n",
    "#         def dijkstra(i, prev):\n",
    "#             cost = [inf] * n\n",
    "#             q = [(0, i, prev)]\n",
    "#             cost[i] = 0\n",
    "#             ans = inf\n",
    "#             while q:\n",
    "#                 pay, cur, prev = heapq.heappop(q)\n",
    "#                 if cost[cur] < pay:\n",
    "#                     continue \n",
    "#                 for nxt in adj[cur]:\n",
    "#                     if nxt != prev:\n",
    "#                         ans = min(ans, pay + cost[nxt] + 1)\n",
    "#                         if cost[nxt] > pay + 1:\n",
    "#                             cost[nxt] = pay + 1\n",
    "#                             heapq.heappush(q, (cost[nxt], nxt, cur))\n",
    "#             return ans\n",
    "        \n",
    "#         ans = inf\n",
    "#         for i in range(n):\n",
    "#             k = dijkstra(i, -1)\n",
    "#             ans = min(ans, k)\n",
    "        \n",
    "#         return ans if ans < inf else -1\n",
    "\n",
    "# 【3】根据数学原理直接推导出来        \n",
    "# class Solution:\n",
    "#     def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "#         ans = n + 1\n",
    "#         visited = [False] * n\n",
    "#         graph = [[] for _ in range(n)]\n",
    "#         for u, v in edges:\n",
    "#             graph[u].append(v)\n",
    "#             graph[v].append(u)\n",
    "#         for i in range(n):\n",
    "#             if not visited[i]:\n",
    "#                 visited[i] = True\n",
    "#                 q = [(i, 0, None)]\n",
    "#                 f = 0\n",
    "#                 candidates = []\n",
    "#                 can_set = set()\n",
    "#                 while f < len(q):\n",
    "#                     x, d, p = q[f]\n",
    "#                     f += 1\n",
    "#                     for v in graph[x]:\n",
    "#                         if v == p:\n",
    "#                             continue\n",
    "#                         if visited[v]:\n",
    "#                             if v not in can_set:\n",
    "#                                 can_set.add(v)\n",
    "#                                 candidates.append(v)\n",
    "#                         else:\n",
    "#                             visited[v] = True\n",
    "#                             q.append((v, d + 1, x))\n",
    "#                 for j in candidates:\n",
    "#                     q = [(j, 0, None)]\n",
    "#                     f = 0\n",
    "#                     dist = {j: 0}\n",
    "#                     while f < len(q):\n",
    "#                         x, d, p = q[f]\n",
    "#                         f += 1\n",
    "#                         if d + d >= ans:\n",
    "#                             break\n",
    "#                         for v in graph[x]:\n",
    "#                             if v == p:\n",
    "#                                 continue\n",
    "#                             if v in dist:\n",
    "#                                 ans = min(ans, dist[v] + d + 1)\n",
    "#                             else:\n",
    "#                                 dist[v] = d + 1\n",
    "#                                 q.append((v, d + 1, x))\n",
    "#         if ans > n:\n",
    "#             return -1\n",
    "#         else:\n",
    "#             return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        visit = [0] * n\n",
    "        ans = float('inf')\n",
    "        adj = [list() for _ in range(n)]\n",
    "\n",
    "        for u, v in edges:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "\n",
    "        def bfs(node):\n",
    "            q = deque([[node, None]])\n",
    "            step = 0\n",
    "            min_length = float('inf')\n",
    "            while q:\n",
    "                t = deque()\n",
    "                while q:\n",
    "                    v, last = q.popleft()\n",
    "                    for u in adj[v]:\n",
    "                        if u == last:\n",
    "                            continue\n",
    "                        if visit[u]:\n",
    "                            min_length = min(min_length, step + visit[u] + 1)\n",
    "                            continue\n",
    "                        visit[u] = step + 1\n",
    "                        t.append([u, v])\n",
    "                if min_length != float('inf'):\n",
    "                    break\n",
    "                q = t\n",
    "                step += 1\n",
    "            return min_length\n",
    "\n",
    "        for i in range(n):\n",
    "            for j in range(n):\n",
    "                visit[j] = 0\n",
    "            res = bfs(i)\n",
    "            ans = min(ans, res)\n",
    "        return ans if ans != float('inf') else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges) -> int:\n",
    "        dic=dict()\n",
    "        for i in edges:\n",
    "            s=dic.get(i[0],set())\n",
    "            s.add(i[1])\n",
    "            dic[i[0]]=s\n",
    "            s=dic.get(i[1],set())\n",
    "            s.add(i[0])\n",
    "            dic[i[1]]=s\n",
    "        next=[]\n",
    "        for i in dic:\n",
    "            if len(dic[i])==1:\n",
    "                next.append(i)\n",
    "        while next!=[]:\n",
    "            now=next[:]\n",
    "            next=[]\n",
    "            for i in now:\n",
    "                for j in dic[i]:\n",
    "                    dic[j].discard(i)\n",
    "                    if len(dic[j])==1:\n",
    "                        next.append(j)\n",
    "                del dic[i]\n",
    "        if dic==dict():\n",
    "            return -1\n",
    "        c=n\n",
    "        for s in dic:\n",
    "            flag=[0]*n\n",
    "            flag[s]=-1\n",
    "            count=1\n",
    "            next={s}\n",
    "            f=1\n",
    "            while next!=set():\n",
    "                count+=2\n",
    "                now=next\n",
    "                next=set()\n",
    "                for i in now:\n",
    "                    for j in dic[i]:\n",
    "                        if j in now:\n",
    "                            f=2\n",
    "                            break\n",
    "                        if j in next and f!=2:\n",
    "                            f=3\n",
    "                        if flag[j]==0:\n",
    "                            flag[j]=-1\n",
    "                            next.add(j)\n",
    "                if f>1:\n",
    "                    if f==2:\n",
    "                        count-=2\n",
    "                    if f==3:\n",
    "                        count-=1\n",
    "                    f=0\n",
    "                    break\n",
    "            c=min(c,count)\n",
    "        return c\n",
    "            \n",
    "        \n",
    "         \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for edge in edges:\n",
    "            g[edge[0]].append(edge[1])\n",
    "            g[edge[1]].append(edge[0])\n",
    "\n",
    "        def bfs(x):\n",
    "            ans=float('inf')\n",
    "            dist=[float('inf') for i in range(n)]\n",
    "            dist[x]=0\n",
    "            dq=deque()\n",
    "            dq.append((x,-1))\n",
    "            while dq:\n",
    "                (node,fa)=dq.popleft()\n",
    "                for new_node in g[node]:\n",
    "                    if dist[new_node]==float('inf'):\n",
    "                        dist[new_node]=1+dist[node]\n",
    "                        dq.append((new_node,node))\n",
    "                    elif new_node!=fa:\n",
    "                        ans=min(ans, dist[new_node]+dist[node]+1)\n",
    "            return ans\n",
    "            \n",
    "        res=float('inf')\n",
    "        for i in range(n):\n",
    "            res=min(res, bfs(i))\n",
    "        if res==float('inf'):\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            visit = [False] * n\n",
    "            queue1 = [i]\n",
    "            queue2 = []\n",
    "            times = 1\n",
    "            while queue1:\n",
    "                for x in queue1:\n",
    "                    visit[x] = True\n",
    "                    for y in graph[x]:\n",
    "                        if visit[y] == False:\n",
    "                            if y in queue1:\n",
    "                                ans = min(ans, times * 2 - 1)\n",
    "                            elif y in queue2:\n",
    "                                ans = min(ans, times * 2)\n",
    "                            else:\n",
    "                                queue2.append(y)\n",
    "                times += 1\n",
    "                queue1 = queue2\n",
    "                queue2 = []\n",
    "        return ans if ans < inf else -1\n",
    "                        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "\n",
    "        g = [[] for i in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(len(g[i])):\n",
    "                q = deque([i])\n",
    "                dis = [inf] * n\n",
    "                dis[i] = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if not (x == i and y==g[i][j]) and dis[y] == inf:\n",
    "                            dis[y] = dis[x] + 1\n",
    "                            q.append(y)\n",
    "                ans = min(ans, 1 + dis[g[i][j]])\n",
    "        \n",
    "        return ans if ans <inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u,v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        def bfs(i):\n",
    "            ans = float('inf')\n",
    "            dist = [-1]*n\n",
    "            dist[i] = 0\n",
    "            q = [i]\n",
    "            level = 1\n",
    "            while q:\n",
    "                tmp = q[:]\n",
    "                q = []\n",
    "                for x in tmp:\n",
    "                    for y in g[x]:\n",
    "                        if dist[y] == -1:\n",
    "                            dist[y] = level\n",
    "                            q.append(y)\n",
    "                        else:\n",
    "                            if dist[y] == dist[x] or dist[y] == dist[x]+1:\n",
    "                                ans = min(ans, dist[x] + dist[y] + 1)\n",
    "                level += 1\n",
    "            return ans\n",
    "        \n",
    "        # 每个点做BFS\n",
    "        min_res = float('inf')\n",
    "        for i in range(n):\n",
    "            loop_len = bfs(i)\n",
    "            if loop_len!=-1:\n",
    "                min_res = min(min_res, loop_len)\n",
    "        return min_res if min_res<float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        nextNode = [[] for x in range(n)]\n",
    "        for i, j in edges:\n",
    "            nextNode[i].append(j)\n",
    "            nextNode[j].append(i)\n",
    "\n",
    "        def bfs(i):\n",
    "            temp = deque([(i, -1)])\n",
    "            res = n + 1\n",
    "            dis = [-1] * n\n",
    "            dis[i] = 0\n",
    "\n",
    "            while temp:\n",
    "                x, fa = temp.popleft()\n",
    "                for y in nextNode[x]:\n",
    "                    if dis[y] < 0:\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        temp.append((y, x))\n",
    "                    elif y != fa:\n",
    "                        res = min(res, dis[x] + dis[y] + 1)\n",
    "            return res\n",
    "\n",
    "        ans = n + 1\n",
    "        for i in range(n):\n",
    "            ans = min(ans, bfs(i))\n",
    "\n",
    "        return ans if ans < n + 1 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        def bfs(start):\n",
    "            ans = inf\n",
    "            dis = [-1] * n\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] == -1:\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y!=fa:\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "        \n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for t in g[i]:\n",
    "                q = deque([i])\n",
    "                dis = [-1] * n\n",
    "                dis[i] = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if not(x==i and y==t) and dis[y] == -1:\n",
    "                            dis[y] = dis[x] + 1\n",
    "                            q.append(y)\n",
    "                if dis[t] != -1:\n",
    "                    ans = min(ans, 1 + dis[t])\n",
    "        \n",
    "        return ans if ans < inf else -1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "\n",
    "        g = [[] for i in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(len(g[i])):\n",
    "                q = deque([i])\n",
    "                dis = [-1] * n\n",
    "                dis[i] = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if not (x == i and y==g[i][j]) and dis[y] == -1:\n",
    "                            dis[y] = dis[x] + 1\n",
    "                            q.append(y)\n",
    "                \n",
    "                if dis[g[i][j]] != -1:\n",
    "                    ans = min(ans, 1 + dis[g[i][j]])\n",
    "        \n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ad = {i:[] for i in range(n)}\n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    " \n",
    "        def bfs(i):\n",
    "            ans=n+1\n",
    "            dis=[-1]*n\n",
    "            dis[i]=0\n",
    "            stack=collections.deque()\n",
    "            stack.append([i,-1])\n",
    "            while stack:\n",
    "                cur,fa=stack.popleft()\n",
    "                for nex in ad[cur]:\n",
    "                    if nex==fa:\n",
    "                        continue\n",
    "                    if dis[nex]==-1:\n",
    "                        dis[nex]=dis[cur]+1\n",
    "                        stack.append([nex,cur])\n",
    "                    else:\n",
    "                        ans=min(ans,dis[cur]+dis[nex]+1)\n",
    "            return ans\n",
    "        res=n+1\n",
    "        for i in range(n):\n",
    "            res=min(res,bfs(i))\n",
    "\n",
    "        if res==n+1:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        degree = [0] * n \n",
    "        for i, (a, b) in enumerate(edges):\n",
    "            g[a].append((b, i))\n",
    "            g[b].append((a, i))\n",
    "\n",
    "        #print(degree)\n",
    "        ans= float('inf')\n",
    "        for i, (a, b) in enumerate(edges):\n",
    "            vis = [0] * n \n",
    "            D = [0] * n \n",
    "            vis[a] = 1\n",
    "            vis[b] = 1 \n",
    "            Q = deque([(0, a,a), (0, b,b)])\n",
    "            while Q:\n",
    "                d, u, fa = Q.popleft()\n",
    "                for v, j in g[u]:\n",
    "                    if i == j or v == fa:\n",
    "                        continue\n",
    "                    if not vis[v]:\n",
    "                        vis[v] = 1\n",
    "                        D[v] = d+1\n",
    "                        Q.append((d+1, v, u))\n",
    "                    else:\n",
    "                        ans = min(ans, d + 1 + D[v]) \n",
    "        return ans + 1 if ans < float('inf') else -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def bfs(start):\n",
    "            ans = inf\n",
    "            dis = [-1] * n # 表示从start到i的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0: # 第一次访问\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append([y, x])\n",
    "                    elif y != fa: # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "\n",
    "        g = [[] for i in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(len(g[i])):\n",
    "                q = deque([i])\n",
    "                dis = [-1] * n\n",
    "                dis[i] = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if not (x == i and y==g[i][j]) and dis[y] == -1:\n",
    "                            dis[y] = dis[x] + 1\n",
    "                            q.append(y)\n",
    "                \n",
    "                if dis[g[i][j]] != -1:\n",
    "                    ans = min(ans, 1 + dis[g[i][j]])\n",
    "        \n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        degree = [0] * n \n",
    "        for i, (a, b) in enumerate(edges):\n",
    "            g[a].append((b, i))\n",
    "            g[b].append((a, i))\n",
    "            degree[a] += 1\n",
    "            degree[b] += 1\n",
    "        Q = deque()\n",
    "        for i in range(n):\n",
    "            if degree[i] == 1:\n",
    "                Q.append(i)\n",
    "        \n",
    "        while Q:\n",
    "            u = Q.popleft()\n",
    "            for v, i in g[u]:\n",
    "                if degree[v] <= 0:\n",
    "                    continue\n",
    "                degree[v] -= 1\n",
    "                degree[u] -= 1\n",
    "                if degree[v] == 1:\n",
    "                    Q.append(v) \n",
    "        #print(degree)\n",
    "        ans= float('inf')\n",
    "        for i, (a, b) in enumerate(edges):\n",
    "            if degree[a] <= 0 or degree[b] <= 0:\n",
    "                continue \n",
    "            vis = [0] * n \n",
    "            D = [0] * n \n",
    "            vis[a] = 1\n",
    "            vis[b] = 1 \n",
    "            Q = deque([(0, a,a), (0, b,b)])\n",
    "            while Q:\n",
    "                d, u, fa = Q.popleft()\n",
    "                for v, j in g[u]:\n",
    "                    if i == j or v == fa:\n",
    "                        continue\n",
    "                    if not vis[v]:\n",
    "                        vis[v] = 1\n",
    "                        D[v] = d+1\n",
    "                        Q.append((d+1, v, u))\n",
    "                    else:\n",
    "                        ans = min(ans, d + 1 + D[v]) \n",
    "        return ans + 1 if ans < float('inf') else -1 \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for a, b in edges:\n",
    "            g[a].append(b)\n",
    "            g[b].append(a) \n",
    "        mn = float('inf')\n",
    "        for a, b in edges:\n",
    "            vis = [0] * n \n",
    "            vis[a] = 1 \n",
    "            Q = deque() \n",
    "            for v in g[a]:\n",
    "                if v != b:\n",
    "                    Q.append((1, v)) \n",
    "                    vis[v] = 1 \n",
    "            while Q:\n",
    "                d, u = Q.popleft() \n",
    "                if u == b:\n",
    "                    mn = min(mn, d) \n",
    "                    break \n",
    "                for v in g[u]:\n",
    "                    if not vis[v]:\n",
    "                        vis[v] = 1\n",
    "                        Q.append((d+1, v)) \n",
    "        return mn + 1 if mn < float('inf') else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            vis = [-1] * n\n",
    "            q = deque()\n",
    "            q.append(start)\n",
    "            c = deque()\n",
    "            while q:\n",
    "                x = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append(y)\n",
    "                    elif vis[y] == -1:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "                vis[x] = 1\n",
    "                c.append(x)\n",
    "            return ans, c\n",
    "\n",
    "        ans, c = min(bfs(i) for i in range(n))\n",
    "        if ans >= inf:\n",
    "            c = deque()\n",
    "        while c:\n",
    "            print(c.popleft())\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "\n",
    "        def bfs(start):\n",
    "            ans = inf\n",
    "            dis = [-1] * n\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:\n",
    "                        ans = min(ans, dis[x] +dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        ans = inf\n",
    "        for u, v in edges:\n",
    "            g[u].append(v)\n",
    "            g[v].append(u)\n",
    "        for start in range(n):\n",
    "            dis = [-1] * n\n",
    "            dis[start] = 0\n",
    "            q = [[start, -1]]\n",
    "            while len(q) > 0:\n",
    "                x, fa = q[0]\n",
    "                q = q[1:]\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append([y, x])\n",
    "                    elif y != fa:\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "        return ans if ans != inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = inf\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for t in g[i]:\n",
    "                q = deque([i])\n",
    "                dis = [-1] * n\n",
    "                dis[i] = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if not(x==i and y==t) and dis[y] == -1:\n",
    "                            dis[y] = dis[x] + 1\n",
    "                            q.append(y)\n",
    "                if dis[t] != -1:\n",
    "                    ans = min(ans, 1 + dis[t])\n",
    "        \n",
    "        return ans if ans < inf else -1\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        e=collections.defaultdict(list)\n",
    "        for a,b in edges:\n",
    "            e[a].append(b)\n",
    "            e[b].append(a)\n",
    "        def dfs(now):\n",
    "            dis=[-1]*n\n",
    "            dis[now]=0\n",
    "            q=collections.deque()\n",
    "            q.append([now,-1])\n",
    "            ret=float(\"inf\")\n",
    "            while q:\n",
    "                tp,fa=q.popleft()\n",
    "                for i in e[tp]:\n",
    "                    if dis[i]==-1:\n",
    "                        dis[i]=dis[tp]+1\n",
    "                        q.append([i,tp])\n",
    "                    elif i!=fa:\n",
    "                        ret=min(ret,dis[i]+dis[tp]+1)\n",
    "            return ret\n",
    "        ans=float(\"inf\")\n",
    "        for i in range(n):\n",
    "            ans=min(dfs(i),ans)\n",
    "        if ans==float(\"inf\"):\n",
    "            return -1\n",
    "        else:\n",
    "            return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = n + 1\n",
    "\n",
    "        g = [[] for i in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        for i in range(n):\n",
    "            for j in range(len(g[i])):\n",
    "                q = deque([i])\n",
    "                dis = [n+1] * n\n",
    "                dis[i] = 0\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if not (x == i and y==g[i][j]) and dis[y] == n+1:\n",
    "                            dis[y] = dis[x] + 1\n",
    "                            # print('x, y, dis[x], dis[y]', x, y, dis[x], dis[y])\n",
    "                            q.append(y)\n",
    "                ans = min(ans, 1 + dis[g[i][j]])\n",
    "        \n",
    "        return -1 if ans > n else ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "\n",
    "        ans = inf\n",
    "\n",
    "        for i in range(n):\n",
    "            for t in g[i]:\n",
    "                dis = [-1] * n\n",
    "                dis[i] = 0\n",
    "                q = deque([i])\n",
    "                while q:\n",
    "                    x = q.popleft()\n",
    "                    for y in g[x]:\n",
    "                        if not(x==i and y==t) and dis[y]==-1:\n",
    "                            dis[y] = dis[x] + 1\n",
    "                            q.append(y)\n",
    "                if dis[t] != -1:\n",
    "                    ans = min(ans, dis[t] + 1)\n",
    "\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g=[[] for _ in range(n)]\n",
    "        for v,u in edges:\n",
    "            g[v].append(u)\n",
    "            g[u].append(v)\n",
    "        \n",
    "        def bfs(x):\n",
    "            ans=inf\n",
    "            dist=[-1]*n\n",
    "            dist[x]=0\n",
    "            q=deque([(x,-1)])\n",
    "            while q:\n",
    "                x,pa=q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dist[y]<0:\n",
    "                        dist[y]=dist[x]+1\n",
    "                        q.append((y,x))\n",
    "                    elif y!=pa:\n",
    "                        ans=min(ans,dist[x]+dist[y]+1)\n",
    "            return ans\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n",
    "        \n",
    "                \n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        @cache\n",
    "        def bfs(i):\n",
    "            q = deque([(i, 0, -1)])\n",
    "            state = [-1] * n\n",
    "            while q:\n",
    "                ai, h, pa = q.popleft()\n",
    "                state[ai] = h\n",
    "                for nex in g[ai]:\n",
    "                    if state[nex] < 0:\n",
    "                        q.append((nex, h+1, ai))\n",
    "                    elif nex != pa:\n",
    "                        return state[nex] + h + 1\n",
    "            return inf\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = collections.defaultdict(list)\n",
    "        for v in edges:\n",
    "            g[v[0]].append(v[1])\n",
    "            g[v[1]].append(v[0])\n",
    "        ans = float('inf')\n",
    "        def bfs(i):\n",
    "            q = collections.deque()\n",
    "            inqueue = [False] * n\n",
    "            dist = [-1] * n\n",
    "            cur = float('inf')\n",
    "            q.append(i)\n",
    "            inqueue[i] = True\n",
    "            dist[i] = 0\n",
    "            while q:\n",
    "                u = q.popleft()\n",
    "                inqueue[u] = False\n",
    "                for v in g[u]:\n",
    "                    if dist[v] == -1:\n",
    "                        q.append(v)\n",
    "                        inqueue[v] = True\n",
    "                        dist[v] = dist[u] + 1\n",
    "                    elif inqueue[v]:\n",
    "                        cur = min(cur, dist[u] + dist[v] + 1)\n",
    "            return cur\n",
    "        for i in range(n):\n",
    "            ans = min(ans, bfs(i))\n",
    "        return -1 if ans == float('inf') else ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)\n",
    "        \n",
    "        def bfs(start):\n",
    "            ans = inf\n",
    "            dis = [-1] * n # 表示从start到i的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0: # 第一次访问\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append([y, x])\n",
    "                    elif dis[y] > 0 and y != fa: # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        self.INF=0x3f3f3f3f\n",
    "        self.adj=defaultdict(set)\n",
    "        for u,v in edges:\t\t\t\t\t\t\t\t#创建邻接表adj\n",
    "            self.adj[u].add(v)\n",
    "            self.adj[v].add(u)\n",
    "        ans=self.INF\n",
    "        for u in range(0,n):\n",
    "            for v in self.adj[u]:\n",
    "                ans=min(ans,self.bfs(n,u,v)+1)\n",
    "        return -1 if ans==self.INF else ans\n",
    "    def bfs(self,n,u,v):\n",
    "        dist=[self.INF]*n\n",
    "        qu=deque()\n",
    "        qu.append(u)\n",
    "        dist[u]=0\n",
    "        while qu:\n",
    "            i=qu.popleft()\n",
    "            for j in self.adj[i]:\n",
    "                if dist[j]==self.INF:\n",
    "                    if i==u and j==v:continue;\n",
    "                    qu.append(j)\n",
    "                    dist[j]=dist[i]+1\n",
    "        return dist[v]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ad = {i:[] for i in range(n)}\n",
    "\n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    " \n",
    "        def bfs(i):\n",
    "            ans=n+1\n",
    "            dis=[-1]*n\n",
    "            dis[i]=0\n",
    "            stack=[[i,-1]]\n",
    "            while stack:\n",
    "                cur,fa = stack.pop(0)\n",
    "                for nex in ad[cur]:\n",
    "                    if nex ==fa:\n",
    "                        continue\n",
    "                    if dis[nex]==-1:\n",
    "                        dis[nex]=dis[cur]+1\n",
    "                        stack.append([nex,cur])\n",
    "                    else:\n",
    "                        ans=min(ans,dis[nex]+dis[cur]+1)\n",
    "            return ans\n",
    "        res=n+1\n",
    "        for i in range(n):\n",
    "            res=min(res,bfs(i))\n",
    "       \n",
    "        return res if res<=n else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            g[x].append(y)\n",
    "            g[y].append(x)  # 建图\n",
    "\n",
    "        def bfs(start: int) -> int:\n",
    "            ans = inf\n",
    "            dis = [-1] * n  # dis[i] 表示从 start 到 i 的最短路长度\n",
    "            dis[start] = 0\n",
    "            q = deque([(start, -1)])\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in g[x]:\n",
    "                    if dis[y] < 0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y, x))\n",
    "                    elif y != fa:  # 第二次遇到\n",
    "                        ans = min(ans, dis[x] + dis[y] + 1)\n",
    "            return ans\n",
    "        ans = min(bfs(i) for i in range(n))\n",
    "        return ans if ans < inf else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 建立临接表\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "        \n",
    "        def dijkstra(i, prev):    # i为起点， pre为上一个点\n",
    "            cost = [inf] * n      # cost[j]代表以i为起点，到j的距离\n",
    "            q = [(0, i, prev)]    # (i到当前点的最小距离, 当前点, 上一个点)\n",
    "            cost[i] = 0\n",
    "            ans = inf\n",
    "            while q:\n",
    "                pay, cur, prev = heapq.heappop(q)\n",
    "                if cost[cur] < pay:\n",
    "                    continue\n",
    "                for nxt in adj[cur]:\n",
    "                    if nxt != prev:\n",
    "                        # pay为i到cur的距离，cost[nxt]为i到nxt的距离，cur和nxt之间的距离为1，正好形成环，更新ans。\n",
    "                        ans = min(ans, pay + cost[nxt] + 1)\n",
    "                        if cost[nxt] > pay + 1:\n",
    "                            cost[nxt] = pay + 1\n",
    "                            heapq.heappush(q, (cost[nxt], nxt, cur))\n",
    "            return ans\n",
    "            \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            k = dijkstra(i, -1)\n",
    "            ans = min(ans, k)\n",
    "            \n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\r\n",
    "        conn: list[set[int]] = [set() for _ in range(n)]\r\n",
    "        for u, v in edges:\r\n",
    "            conn[u].add(v)\r\n",
    "            conn[v].add(u)\r\n",
    "        \r\n",
    "        def cirLen(e: list[int]) -> int:\r\n",
    "            ret = -1\r\n",
    "            conn[e[0]].remove(e[1])\r\n",
    "            conn[e[1]].remove(e[0])\r\n",
    "            vis: set[int] = set()\r\n",
    "            q = deque([(e[0], 1)])\r\n",
    "            while q:\r\n",
    "                node, d = q.popleft()\r\n",
    "                if node == e[1]:\r\n",
    "                    ret = d\r\n",
    "                    break\r\n",
    "                for nxt in conn[node]:\r\n",
    "                    if nxt not in vis:\r\n",
    "                        vis.add(nxt)\r\n",
    "                        q.append((nxt, d + 1))\r\n",
    "            conn[e[0]].add(e[1])\r\n",
    "            conn[e[1]].add(e[0])\r\n",
    "            return ret\r\n",
    "        \r\n",
    "        return min(map(cirLen, edges), key=lambda x: 1001 if x == -1 else x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import defaultdict, deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # https://leetcode.cn/problems/shortest-cycle-in-a-graph/solutions/2203585/yi-tu-miao-dong-mei-ju-qi-dian-pao-bfspy-ntck/\n",
    "        # 预处理邻接表\n",
    "        t =  defaultdict(set)\n",
    "        for n1,n2 in edges:\n",
    "            t[n1].add(n2)\n",
    "            t[n2].add(n1)\n",
    "        print(t)\n",
    "        \n",
    "        res = 10**9\n",
    "        \n",
    "        for v in t:\n",
    "            level = 1\n",
    "            dis = [-1]*n  # 从v到i的最短路长度\n",
    "            dis[v] = 0\n",
    "            q = deque([(v,-1)])  # 初始化队列，(结点, 上次遇到的父结点)\n",
    "            while q:\n",
    "                x, fa = q.popleft()\n",
    "                for y in t[x]:\n",
    "                    if dis[y]<0:  # 第一次遇到\n",
    "                        dis[y] = dis[x] + 1\n",
    "                        q.append((y,x))\n",
    "                    elif y!=fa:  # 第二次遇到\n",
    "                        res = min(res, dis[x]+dis[y]+1)\n",
    "        \n",
    "        return res if res < 10000 else -1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # https://oi-wiki.org/graph/shortest-path/#dijkstra-%E7%AE%97%E6%B3%95\n",
    "        # 建立临接表\n",
    "        adj = [[] for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            adj[u].append(v)\n",
    "            adj[v].append(u)\n",
    "        \n",
    "        # 返回包含节点i的最小环\n",
    "        def dijkstra(i):    # i为起点， pre为上一个点\n",
    "            cost = [inf] * n      # cost[j]代表以i为起点，到j的距离\n",
    "            q = [(0, i, -1)]    # (i到当前点的最小距离, 当前点, 上一个点)\n",
    "            cost[i] = 0\n",
    "            ans = inf\n",
    "            while q:\n",
    "                pay, cur, prev = heapq.heappop(q)\n",
    "                if cost[cur] < pay:\n",
    "                    continue\n",
    "                for nxt in adj[cur]:\n",
    "                    if nxt != prev:\n",
    "                        # pay为i到cur的距离，cost[nxt]为i到nxt的距离，cur和nxt之间的距离为1，正好形成环，更新ans。\n",
    "                        ans = min(ans, pay + cost[nxt] + 1)\n",
    "                        if cost[nxt] > pay + 1:\n",
    "                            cost[nxt] = pay + 1\n",
    "                            heapq.heappush(q, (cost[nxt], nxt, cur))\n",
    "            return ans\n",
    "            \n",
    "        ans = inf\n",
    "        for i in range(n):\n",
    "            k = dijkstra(i)\n",
    "            ans = min(ans, k)\n",
    "            \n",
    "        return ans if ans < inf else -1\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ans = float('inf')\n",
    "        e = defaultdict(set)\n",
    "        for u,v in edges:\n",
    "            e[u].add(v)\n",
    "            e[v].add(u)\n",
    "        for u,v in edges:\n",
    "            dis = [-1 for _ in range(n)]\n",
    "            dis[u] = 0\n",
    "            q = deque([u])\n",
    "            while q:\n",
    "                cur = q.popleft()\n",
    "                for nxt in e[cur]:\n",
    "                    if (cur == u and nxt == v or cur == v and nxt == u):\n",
    "                        continue\n",
    "                    if dis[nxt] != -1:\n",
    "                        continue\n",
    "                    dis[nxt] = dis[cur] + 1\n",
    "                    q.append(nxt)\n",
    "            if dis[v] != -1:\n",
    "                ans = min(ans,dis[v] + 1)\n",
    "        return ans if ans != float('inf') else -1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        g = defaultdict(list) \n",
    "        for i, (a, b) in enumerate(edges):\n",
    "            g[a].append((b, i))\n",
    "            g[b].append((a, i)) \n",
    "        \n",
    "        ans = float('inf')\n",
    "        for i, (a,b) in enumerate(edges):\n",
    "            vis = [0] * n \n",
    "            vis[a] = 1\n",
    "            Q = deque([(0, a)])\n",
    "            while Q:\n",
    "                d, u = Q.popleft() \n",
    "                if u == b:\n",
    "                    ans= min(ans, d+1) \n",
    "                    break \n",
    "                for v, j in g[u]:\n",
    "                    if j == i or vis[v]:\n",
    "                        continue \n",
    "                    vis[v] = 1\n",
    "                    Q.append((d+1, v))\n",
    "        return ans if ans < float('inf') else -1 "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        ad = {i:[] for i in range(n)}\n",
    "        for s,e in edges:\n",
    "            ad[s].append(e)\n",
    "            ad[e].append(s)\n",
    " \n",
    "        def bfs(i):\n",
    "            ans=n+1\n",
    "            dis=[-1]*n\n",
    "            dis[i]=0\n",
    "            stack=[[i,-1]]\n",
    "            while stack:\n",
    "                cur,fa=stack.pop(0)\n",
    "                for nex in ad[cur]:\n",
    "                    if nex==fa:\n",
    "                        continue\n",
    "                    if dis[nex]==-1:\n",
    "                        dis[nex]=dis[cur]+1\n",
    "                        stack.append([nex,cur])\n",
    "                    else:\n",
    "                        ans=min(ans,dis[cur]+dis[nex]+1)\n",
    "            return ans\n",
    "        res=n+1\n",
    "        for i in range(n):\n",
    "            res=min(res,bfs(i))\n",
    "\n",
    "        if res==n+1:\n",
    "            return -1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self._set = defaultdict(lambda: None)\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        while self._set[root] != None:\n",
    "            root = self._set[root]\n",
    "        while x != root:\n",
    "            original_father = self._set[x]\n",
    "            self._set[x] = root\n",
    "            x = original_father\n",
    "        return root\n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx != ry:\n",
    "            self._set[rx] = ry\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 先找连通的区域，然后对于每个连通区域：\n",
    "        # 1、 去掉最后构成连通区域的那条边（start， end）\n",
    "        # 2、用BFS，从start出发，每一步走所有邻居，则可以得到走多少步后到end\n",
    "        # 3、则该连通区域的最小环为步长+1\n",
    "        uf = UnionFind()\n",
    "\n",
    "        # 记录最后形成环的那条边\n",
    "        tw = []\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "            if uf.find(x) == uf.find(y):\n",
    "                tw.append([x, y])\n",
    "            uf.union(x, y)\n",
    "        \n",
    "        res = inf\n",
    "        for x, y in tw:\n",
    "            # cur为x所有的邻居(除了y)，相当于去掉x，y这条边\n",
    "            cur = [nxt for nxt in graph[x] if nxt != y]\n",
    "            passed = set(cur) | {x}\n",
    "            \n",
    "            for i in range(3, min(res, 1001)):\n",
    "                # 从3开始是因为最小环为3\n",
    "                nxt = set()\n",
    "                \n",
    "                for n in cur:\n",
    "                    # m为x邻居(除了y)的邻居\n",
    "                    for m in graph[n]:\n",
    "                        if m not in passed:\n",
    "                            nxt.add(m)\n",
    "                            passed.add(m)\n",
    "                # 剪枝\n",
    "                if y in nxt:\n",
    "                    res = min(res, i)\n",
    "                    break\n",
    "                if not nxt:\n",
    "                    break\n",
    "                cur = nxt\n",
    "                \n",
    "        if res is inf:\n",
    "            return -1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self._set = defaultdict(lambda: None)\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        while self._set[root] != None:\n",
    "            root = self._set[root]\n",
    "        while x != root:\n",
    "            original_father = self._set[x]\n",
    "            self._set[x] = root\n",
    "            x = original_father\n",
    "        return root\n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx != ry:\n",
    "            self._set[rx] = ry\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        uf = UnionFind()\n",
    "        \n",
    "        tw = []\n",
    "        \n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "            if uf.find(x) == uf.find(y):\n",
    "                tw.append([x, y])\n",
    "            uf.union(x, y)\n",
    "        \n",
    "        print(tw)\n",
    "        res = inf\n",
    "        for x, y in tw:\n",
    "            cur = [nxt for nxt in graph[x] if nxt != y]\n",
    "            passed = set(cur) | {x}\n",
    "            \n",
    "            for i in range(3, min(res, 1005)):\n",
    "                nxt = set()\n",
    "                \n",
    "                for n in cur:\n",
    "                    for m in graph[n]:\n",
    "                        if m not in passed:\n",
    "                            nxt.add(m)\n",
    "                            passed.add(m)\n",
    "                            \n",
    "                # print(passed, cur, nxt, res, i)\n",
    "                \n",
    "                if y in nxt:\n",
    "                    res = min(res, i)\n",
    "                    break\n",
    "                if not nxt:\n",
    "                    break\n",
    "                \n",
    "                \n",
    "                cur = nxt\n",
    "                \n",
    "        \n",
    "        if res is inf:\n",
    "            return -1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        m = len(edges)\n",
    "\n",
    "        graph = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "\n",
    "        res = inf\n",
    "\n",
    "        for i in range(m):\n",
    "            s, e = edges[i]\n",
    "\n",
    "            que = deque()\n",
    "            que.append((s, 0))\n",
    "\n",
    "            visited = set()\n",
    "            visited.add(s)\n",
    "\n",
    "            while que:\n",
    "                u, dist = que.popleft()\n",
    "\n",
    "                if u == e:\n",
    "                    res = min(res, dist)\n",
    "\n",
    "                for v in graph[u]:\n",
    "                    if (u == s and v == e) or (u == e and v == s):\n",
    "                        continue\n",
    "                    if v not in visited:\n",
    "                        visited.add(v)\n",
    "                        que.append((v, dist + 1))\n",
    "\n",
    "        return res + 1 if res < inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class UnionFind:\n",
    "    def __init__(self):\n",
    "        self._set = defaultdict(lambda: None)\n",
    "    def find(self, x):\n",
    "        root = x\n",
    "        while self._set[root] != None:\n",
    "            root = self._set[root]\n",
    "        while x != root:\n",
    "            original_father = self._set[x]\n",
    "            self._set[x] = root\n",
    "            x = original_father\n",
    "        return root\n",
    "    def union(self, x, y):\n",
    "        rx, ry = self.find(x), self.find(y)\n",
    "        if rx != ry:\n",
    "            self._set[rx] = ry\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        # 先找连通的区域，然后对于每个连通区域：\n",
    "        # 1、 去掉最后构成连通区域的那条边（start， end）\n",
    "        # 2、用BFS，从start出发，每一步走所有邻居，则可以得到走多少步后到end\n",
    "        # 3、则该连通区域的最小环为步长+1\n",
    "        uf = UnionFind()\n",
    "\n",
    "        # 记录最后形成环的那条边\n",
    "        tw = []\n",
    "        graph = [[] for _ in range(n)]\n",
    "        for x, y in edges:\n",
    "            graph[x].append(y)\n",
    "            graph[y].append(x)\n",
    "        \n",
    "            if uf.find(x) == uf.find(y):\n",
    "                tw.append([x, y])\n",
    "            uf.union(x, y)\n",
    "        \n",
    "        res = inf\n",
    "        for x, y in tw:\n",
    "            # cur为x所有的邻居(除了y)，相当于去掉x，y这条边\n",
    "            cur = [nxt for nxt in graph[x] if nxt != y]\n",
    "            passed = set(cur) | {x}\n",
    "            \n",
    "            for i in range(3, min(res, 1001)):\n",
    "                # 从3开始是因为最小环为3\n",
    "                nxt = set()\n",
    "                \n",
    "                for n in cur:\n",
    "                    # m为x邻居(除了y)的邻居\n",
    "                    for m in graph[n]:\n",
    "                        if m not in passed:\n",
    "                            nxt.add(m)\n",
    "                            passed.add(m)\n",
    "                # 剪枝\n",
    "                if y in nxt:\n",
    "                    res = min(res, i)\n",
    "                    break\n",
    "                if not nxt:\n",
    "                    break\n",
    "                cur = nxt\n",
    "                \n",
    "        if res is inf:\n",
    "            return -1\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        graph = [set() for _ in range(n)]\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "        res = float('inf')\n",
    "        for i in range(n):\n",
    "            res = min(res, self.process(n, graph, i))\n",
    "        if res == float('inf'):\n",
    "            return -1\n",
    "        return res\n",
    "\n",
    "    def process(self, n, graph, root):\n",
    "        level = [-1] * n\n",
    "        prev = [-1] * n\n",
    "        from collections import deque\n",
    "        queue = deque([root])\n",
    "        level[root] = 0\n",
    "        while queue:\n",
    "            u = queue.popleft()\n",
    "            res = float('inf')\n",
    "            for v in graph[u]:\n",
    "                if prev[u] != v:\n",
    "                    if level[v] != -1:\n",
    "                        res = min(res, level[v] + level[u] + 1)\n",
    "                    else:\n",
    "                        level[v] = level[u] + 1\n",
    "                        queue.append(v)\n",
    "                        prev[v] = u\n",
    "            if res != float('inf'):\n",
    "                return res\n",
    "        return float('inf')"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, e: List[List[int]]) -> int:\n",
    "        g = defaultdict(list)\n",
    "        for i, j in e:\n",
    "            g[i].append(j)\n",
    "            g[j].append(i)\n",
    "        def bfs(x):\n",
    "            s = [(x, -1)]\n",
    "            v = {j:-1 for j in range(n)}\n",
    "            v[-1] = -1\n",
    "            ans = float('inf')\n",
    "            while s:\n",
    "                tmp = []\n",
    "                for j, fa in s:\n",
    "                    if v[j]==-1:\n",
    "                        v[j] = v[fa] + 1 \n",
    "                        for k in g[j]:\n",
    "                            if k!=fa:\n",
    "                                tmp.append((k, j))\n",
    "                    else:\n",
    "\n",
    "                        ans = min(ans, v[fa]+1+v[j]) \n",
    "                s = tmp\n",
    "            return ans \n",
    "        ans = [bfs(j) for j in range(n)]\n",
    "        # print(ans)\n",
    "        if min(ans)==float('inf'):\n",
    "            return -1 \n",
    "        return min(ans)\n",
    "\n",
    "                    \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "        m = len(edges)\n",
    "\n",
    "        graph = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "\n",
    "        res = inf\n",
    "\n",
    "        for s, e in edges:\n",
    "\n",
    "            que = deque()\n",
    "            que.append((s, 0))\n",
    "\n",
    "            visited = set()\n",
    "            visited.add(s)\n",
    "\n",
    "            while que:\n",
    "                u, dist = que.popleft()\n",
    "\n",
    "                for v in graph[u]:\n",
    "                    if u == s and v == e:\n",
    "                        continue\n",
    "                        \n",
    "                    if v == e:\n",
    "                        res = min(res, dist + 1)\n",
    "                        break\n",
    "                        \n",
    "                    if v not in visited:\n",
    "                        visited.add(v)\n",
    "                        que.append((v, dist + 1))\n",
    "\n",
    "        return res + 1 if res < inf else -1\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def findShortestCycle(self, n: int, edges: List[List[int]]) -> int:\n",
    "\n",
    "        graph = defaultdict(set)\n",
    "        for u, v in edges:\n",
    "            graph[u].add(v)\n",
    "            graph[v].add(u)\n",
    "\n",
    "        res = inf\n",
    "\n",
    "        for s, e in edges:\n",
    "            que = deque()\n",
    "            que.append((s, 0))\n",
    "\n",
    "            visited = set()\n",
    "            visited.add(s)\n",
    "\n",
    "            while que:\n",
    "                u, dist = que.popleft()\n",
    "\n",
    "                for v in graph[u]:\n",
    "                    if v == e:\n",
    "                        if u == s:\n",
    "                            continue\n",
    "\n",
    "                        res = min(res, dist + 1)\n",
    "                        break\n",
    "\n",
    "                    if v not in visited:\n",
    "                        visited.add(v)\n",
    "                        que.append((v, dist + 1))\n",
    "\n",
    "        return res + 1 if res < inf else -1\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
